//
//  Leetcode01.swift
//  DataSructure
//
//  Created by Clover on 2020/6/8.
//  Copyright © 2020 Clover. All rights reserved.
//

import Cocoa

class Leetcode01: NSObject {

}

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var left = 0 ,mid = 0, right = nums.count - 1
        while left <= right {
            mid = (right - left)/2 + left
            if nums[mid] == target{
                return mid
            }else if nums[mid] < target{
                left = mid + 1
            }else{
                right = mid - 1
            }
        }
        return -1
    }
    
    
    func mySqrt(_ x: Int) -> Int {
        if (x == 0) {
            return 0
        }
        //二分法
        var left = 1, right = x, mid = (left+right)/2;
        while(left < right && mid != left)
        {
            if(mid == x/mid)
            {
                return mid;
            }else if(mid < x / mid)
            {
                left = mid;
                mid = (left + right) / 2;
            }
            else
            {
                right = mid;
                mid = (left + right) / 2;
            }
        }
        return left;
    }
    
    func guess(_ num: Int) -> Int {
        let value = 2
        if num > value {
            return -1
        }else if num < value{
            return 1
        }else {
            return 0
        }
    }
    
    func guessNumber(_ n: Int) -> Int {
        var left = 1, right = n;
        while true {
           let mid = (right - left)/2 + left
            if guess(mid) == 0 {
                return mid
            }else if guess(mid) < 0{
                right = mid - 1
            }else{
                left = mid + 1
            }
        }
    }
    
    func searchNums(_ nums: [Int], _ target: Int) -> Int {
        if nums.count == 1 {
            return nums[0] == target ? 0 : -1;
        }
        
        var left = 0, right = nums.count - 1
        while left <= right{
            let mid = (right + left) / 2
            if nums[mid] == target{
                return mid
            }
            
            if nums[0] <= nums[mid]{// 左边有序
                if nums[0] <= target && target < nums[mid]{// 在左侧区间内
                    right = mid - 1
                }else{// 在右侧区间
                    left = mid + 1
                }
            }else{// 右侧有序
                if  nums[mid] < target && target <= nums.last!{// 右侧区间内
                    left = mid + 1
                }else{// 左侧区间 无序
                    right = mid - 1
                }
            }
        }
        return -1
    }
    
    func firstBadVersion(_ n: Int) -> Int {
        var left = 0 ,right = n
        while left < right{
            let mid = (right - left) / 2 + left
            if mid == n{
                return mid
            }else if(mid > n){
                right = mid
            }else{
                left = mid + 1
            }
        }
        if left == n {return left}
        return -1
    }
    
    func isUnique(_ astr: String) -> Bool {
        if astr.count == 0 {
            return false
        }
        
        var mapDic = [Character: Int]()
        for char in astr{
            if mapDic.keys.contains(char) {
                return false
            }else{
                mapDic.updateValue(1, forKey: char)
            }
        }
        return true
    }
//    面试题 01.02. 判定是否互为字符重排
    func CheckPermutation(_ s1: String, _ s2: String) -> Bool {
        if s1.count != s2.count {
            return false
        }
        let new_s1 = s1.sorted(by: <)
        let new_s2 = s2.sorted(by: <)
        if new_s1 == new_s2 {
            return true
        }
        
        return false
    }
    
    func replaceSpaces(_ S: String, _ length: Int) -> String {
        
        return ""
    }
}
